package 题目集.归并;

import java.util.Scanner;

public class ch01_逆序对数量 {
    static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        nums = new int[sc.nextInt()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(fun(0, nums.length - 1));
    }

    //返回lr上，有多少个逆序对
    public static long fun(int l, int r) {
        if (l == r) return 0;
        int mid = l + (r - l >> 1);
        long left = fun(l, mid);
        long right = fun(mid + 1, r);
        long merge = merge(l, mid, r);
        return left + right + merge;
    }

    public static long merge(int l, int mid, int r) {
        long res = 0;  //产生的逆序对
        int[] temp = new int[r - l + 1];
        int i = l, j = mid + 1;
        int x = 0;
        while (i <= mid && j <= r) {
            if (nums[i] > nums[j]) {
                res += mid - i + 1;
                temp[x++] = nums[j++];
            } else {
                temp[x++] = nums[i++];
            }
        }
        while (i <= mid) {
            temp[x++] = nums[i++];
        }
        while (j <= r) {
            temp[x++] = nums[j++];
        }
        for (int k = 0; k < temp.length; k++) {
            nums[l + k] = temp[k];
        }
        return res;
    }

}
